#include <iostream>
#include <string>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
using namespace std;

int n, m;
int a, b, c;
int k = 0;
int maxlen = 0x3f3f3f;

struct edge
{
    int b, c;
    bool visited;
};

vector<edge> g[1010*2];
bool vis[1010 * 2];

void dfs(int begin, int dis, int changecount, int len)
{
    if (begin == dis)
    {
        if (len <= maxlen)
        {
            int breakpoint = 0;
            for (int i = 1; i <= m; i++)
            {
                for (auto &e : g[i])
                {
                    if (!e.visited && e.c)
                    {
                        breakpoint++;
                    } //找到需要毁坏的边
                }
            }
            breakpoint /= 2 ; //进行去重处理
            int temp = breakpoint + changecount;
            if(maxlen==len){
                if(temp<k){
                    k = temp;
                }
            }
            else k = temp;
            maxlen = len;
        }
        return;
    }
    for (auto &e : g[begin])
    {
        if (!vis[e.b])
        {
            e.visited = true;
            edge* temp = nullptr;
            for(auto& f:g[e.b]){
                if(f.b==begin){
                    temp = &f;
                    f.visited = true;
                    break;
                }
            } //将对应的边标记为已访问
            vis[e.b] = true;
            if (e.c == 0)
                dfs(e.b, dis, changecount + 1, len + 1);
            else
                dfs(e.b, dis, changecount, len + 1);
            vis[e.b] = false;
            temp->visited = false;
            e.visited = false;
        }
    }
    return;
}

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        cin >> a >> b >> c;
        g[a].push_back({b, c, false});
        g[b].push_back({a, c, false}); //双向图
    }
    vis[1] = true;
    dfs(1, n, 0, 0);
    cout << k << endl;
   // system("pause");
    return 0;
}
